package com.hdu.other.dp.three;

public class lc688 {
    class Solution {
        public double knightProbability(int n, int k, int row, int column) {
            double[][][] dp = new double[k + 1][n][n];
            for (int i = 0; i < k + 1; i++)
                for (int j = 0; j < n; j++)
                    for (int m = 0; m < n; m++)
                        dp[i][j][m] = -1;
            return f(n, k, row, column, dp);
        }


        double f(int n, int k, int row, int column, double[][][] dp) {
            if (row < 0 || row >= n || column < 0 || column >= n)
            {
                return 0;
            }
            if (k == 0)
            {
                return 1;
            }
            if (dp[k][row][column] != -1)
            {
                return dp[k][row][column];
            }
            double res = 0;
            res += f(n, k - 1, row - 2, column - 1, dp) / 8;
            res += f(n, k - 1, row - 2, column + 1, dp) / 8;
            res += f(n, k - 1, row - 1, column - 2, dp) / 8;
            res += f(n, k - 1, row - 1, column + 2, dp) / 8;
            res += f(n, k - 1, row + 1, column - 2, dp) / 8;
            res += f(n, k - 1, row + 1, column + 2, dp) / 8;
            res += f(n, k - 1, row + 2, column - 1, dp) / 8;
            res += f(n, k - 1, row + 2, column + 1, dp) / 8;
            dp[k][row][column] = res;
            return res;
        }
    }
}
